package pacman;

/**
 * This class run the Dijkstra search algorithm in the map to find the minimun path to the pacman
 * @author Carlos Massera Filho
 */
public class Dijkstra
{
  private int[][] costMatrix;
  private int[][] weightMatrix;
  private Maps map;
  private int size, sizeX, sizeY;

  /**
   * Start the dijikstra variables, sets the size of the costMatrix
   * @param map The map where the algorithm will run
   * @param sizeX The size of the map where the algorithm will run
   * @param sizeY The size of the map where the algorithm will run
   * @param size The width of a block of the map
   */
  public Dijkstra(Maps map, int sizeX, int sizeY, int size)
  {
    this.size = size;
    this.sizeX = sizeX;
    this.sizeY = sizeY;
    this.costMatrix = new int[sizeX][sizeY];
    this.weightMatrix = new int[sizeX][sizeY];

    this.map = map;

    eraseWeightMatrix();
  }
  
  private void costMatrixFiller(int currentX, int currentY, int posCost)
  {
    if (map.getMap()[currentX][currentY].isPassable() == false)
    {
      this.costMatrix[currentX][currentY] = -1;
      return;
    }
    this.costMatrix[currentX][currentY] = posCost;

    if (currentX - 1 >= 0)
    {
      if(this.costMatrix[currentX - 1][currentY] > posCost)
        costMatrixFiller(currentX - 1, currentY, posCost + weightMatrix[currentX - 1][currentY]);
    }
    else
      if(this.costMatrix[sizeX - 1][currentY] > posCost)
        costMatrixFiller(sizeX - 1, currentY, posCost + weightMatrix[sizeX - 1][currentY]);

    if (currentY - 1 >= 0)
    {
      if(this.costMatrix[currentX][currentY - 1] > posCost)
        costMatrixFiller(currentX, currentY - 1, posCost + weightMatrix[currentX][currentY - 1]);
    }
    else
      if(this.costMatrix[currentX][sizeY - 1] > posCost)
        costMatrixFiller(currentX, sizeY - 1, posCost + weightMatrix[currentX][sizeY - 1]);

    if (currentX + 1 < sizeX)
    {
      if(this.costMatrix[currentX + 1][currentY] > posCost)
        costMatrixFiller(currentX + 1, currentY, posCost + weightMatrix[currentX + 1][currentY]);
    }
    else
      if(this.costMatrix[0][currentY] > posCost)
        costMatrixFiller(0, currentY, posCost + weightMatrix[0][currentY]);

    if (currentY + 1 < sizeY)
    {
      if(this.costMatrix[currentX][currentY + 1] > posCost)
        costMatrixFiller(currentX, currentY + 1, posCost + weightMatrix[currentX][currentY]);
    }
    else
      if(this.costMatrix[currentX][0] > posCost)
        costMatrixFiller(currentX, 0, posCost + weightMatrix[currentX][0]);
  }

  /**
   * Start the costMatrix then call the recursive Dijkstra algorithm
   * @param pacmanX Pacman X position
   * @param pacmanY Pacman Y position
   */
  public void createCostMatrix(int pacmanX, int pacmanY)
  {
    for (int i = 0; i < sizeX; i++)
      for(int j = 0; j < sizeY; j++)
        costMatrix[i][j] = 100000;
    costMatrixFiller(pacmanX/size, pacmanY/size, 0);
  }

  /**
   * Clear the weight matrix to reset the algorithm
   */
  public void eraseWeightMatrix()
  {
    for (int i = 0; i < sizeX; i++)
      for(int j = 0; j < sizeY; j++)
        weightMatrix[i][j] = 1;
  }

  /**
   * Locate the minimum path from position x,y to pacman and increase the weight
   * from last cell before pacman in 1000 units to force the algorithm to seek
   * new paths
   * @param x
   * @param y
   */
  public void updateWeight(int x, int y)
  {
    if (costMatrix[x][y] % 1000 == 1)
    {
      weightMatrix[x][y] += 1000;
      return;
    }

    if (x - 1 >= 0)
    {
      if (costMatrix[x][y] - 1 == costMatrix[x - 1][y])
        updateWeight(x - 1, y);
    }
    else
      if (costMatrix[x][y] - 1 == costMatrix[sizeX - 1][y])
        updateWeight(sizeX - 1, y);

    if (x + 1 < sizeX)
    {
      if (costMatrix[x][y] - 1 == costMatrix[x + 1][y])
        updateWeight(x + 1, y);
    }
    else
      if (costMatrix[x][y] - 1 == costMatrix[0][y])
        updateWeight(0, y);

    if (y - 1 >= 0)
    {
      if (costMatrix[x][y] - 1 == costMatrix[x][y - 1])
        updateWeight(x, y - 1);
    }
    else
      if (costMatrix[x][y] - 1 == costMatrix[x][sizeY - 1])
        updateWeight(x, sizeY - 1);

    if (y + 1 < sizeY)
    {
      if (costMatrix[x][y] - 1 == costMatrix[x][y + 1])
        updateWeight(x, y + 1);
    }
    else
      if (costMatrix[x][y] - 1 == costMatrix[x][0])
        updateWeight(x, 0);
  }

  /**
   * Prints in text mode the walk cost matrix
   */
  public void printCostMatrix()
  {
    for(int i = 0; i < sizeY; i++)
    {
      for(int j = 0; j < sizeX; j++)
        if(this.costMatrix[j][i] < 10 && this.costMatrix[j][i] >= 0)
          System.out.print(this.costMatrix[j][i] % 1000 + "  ");
        else
          if (this.costMatrix[j][i] == 100000)
            System.out.print("   ");
          else
            System.out.print(this.costMatrix[j][i] % 1000 + " ");
      System.out.println();
    }
    System.out.println();
  }

  /**
   * Get the walking cost of the position (x, y)
   *
   * The division exist to fit to block size map
   * @param x Position x of the cell
   * @param y Position y of the cell
   * @return the cost from  position (x, y)
   */
  public int getPosistionCost(int x, int y)
  {
    return costMatrix[x/size][y/size];
  }
}
